class Node{
    public int val;
    public Node next;
    public Node(int val) {
        this.val = val;
    }
}

public class LinkedList {
    public Node head = null;

    //头插
    public void addFirst(int val) {
        Node node = new Node(val);
        node.next = this.head;
        this.head = node;
    }

    public void show(){
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.val +" ");
            cur = cur.next;
        }
    }

    public void show2(Node newHead){
        Node cur = newHead;
        while (cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

    /**
     * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，
     * 重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
     *
     * @return
     */
    public Node deleteDuplication() {
        Node cur = this.head;
        Node tmpHead = new Node(-1);
        Node newHead = tmpHead;
        while (cur != null) {
            //有重复时
            if (cur.next != null && cur.val == cur.next.val) {
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                cur = cur.next;
            }else {
                tmpHead.next = cur;
                tmpHead = tmpHead.next;
                cur = cur.next;
            }

        }
        tmpHead.next = null;
        return newHead.next;
    }

    /**
     *链表的回文结构
     */
    public boolean chkPalindrome() {
        if (this.head == null) return false;
        if (this.head.next == null) return true;
        Node fast = this.head;
        Node slow = this.head;
        //找中间值
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //反转slow后半部分
        Node cur = slow.next;
        while (cur != null) {
            Node curNext = cur.next;
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        while (this.head != slow) {
            if (this.head.val != slow.val){
                return false;
            }
            //偶数时
            if (this.head.next == slow) {
                return true;
            }
            this.head = this.head.next;
            slow = slow.next;
        }
        return true;
    }

    /**
     *  给定一个链表，判断链表中是否有环。
     * @return
     */
    public boolean hasCycle1() {
        Node fast = this.head;
        Node slow = this.head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                return true;
            }
        }
        return false;
    }

    /**
     * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
     */
    public Node detectCycle() {
        Node fast = this.head;
        Node slow = this.head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (fast == slow) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow =this.head;
        while (slow != fast){
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }



}
